\section{Introdução}
\label{introducao}

O problema do caxeiro-viajante (PCV) retrata um desafio antigo: construir uma rota que, dada $n$ cidades, se inicie em uma determinada cidade passando pelas demais uma única vez e retornando à origem (ciclo Hamiltoniano).  Apenas em meados de 1930, o PCV tomou rigor matemático, vindo a ser explorado computacionalmente no final do século XX em diante.  Vários textos retratam a relevância histórica e a descrição matemática deste problema. Os trabalhos de Applegate et al.l~\cite{applegate} e Gutin et Al.~\cite{gutin} são as principais referências desta introdução.

 A formulação matemática precisa do PCV pode ser descrita da seguinte forma: dado um digrafo completo, $(K_{n}, c)$, encontrar um ciclo Hamiltoniano em $K_{n}$ de custo mínimo. $c$ é uma função de custo onde, para dado arco $(x, y)$ o valor do custo de encaminhamento é dado por $c(x, y)$.

O PCV apresenta uma descrição simples mas, no entanto, não se encontra uma solução ótima em tempo hábil. Gutin et Al.~\cite{gutin} explora diversas soluções em que os limites superiores sempre esbarram em tempos não-polinomiais. Ainda, os algoritmos que executam em tempo polinomiais descritos por Applegate et Al.~\cite{applegate} não são capazes de encontrar soluções ótimas, apenas soluções próximas a isto.

Uma outra possível solução para o PCV, se dá na aplicação de algoritmos genéticos (AG). AG é uma técnica de busca por soluções descrita inicialmente por Goldberg~\cite{goldberg}. O AG se baseia nas estratégias de cruzamento e mutação da biologia, e que permite realizar uma busca pelas melhores soluções de determinados problemas. O AG inicia uma população de estruturas (indivíduos), onde cada indivíduo representa um possível solução. A cada geração, indivíduos sofrem alterações através de operadores genéticos (comumente: cruzamento e mutação), para então passarem por um mecanismo de seleção natural. Este mecanismo de seleção natural define quais os indivíduos aptos que representarão uma nova geração.

Utilizar AG permite a busca limitada no espaço de estados de soluções. Mesmo que nem todas as possíveis soluções sejam avaliadas, um AG permite tentar melhorar as soluções existentes nos indivíduos (realizando cruzamento) e evitando que haja viés por uma solução que domine uma população (através de mutação). Estas duas características tornam atraentes as soluções que utilizem AG para o PCV, pois é um problema que explora um vasto espaço de soluções.

Cada indivíduo apresenta uma sequência de genes que representam, cada um, parte da solução. Uma das formas de representar o indivíduo de um AG que resolva o PCV, é dizer que o primeiro gene armazena a primeira cidade a ser visitada, o segundo gene, a segunda cidade, e assim sucessivamente. Os operadores genéticos alteram essa informação, buscando testar diversas soluções possíveis. E os seletores naturais atuam obtendo os indivíduos que sejam mais aptos a estarem próximos de uma solução. Esta seleção faz uso de uma função de avaliação, conhecida como \textit{função de fitness}. Para o PCV, a \textit{função de fitness} poderia ser expressa como a função que retorna o custo total do encaminhamento representado por um indivíduo.

Este relatório analisa diversas possiblidades de estratégias a serem utilizadas durante uma implementação de uma solução do PCV através de AG, em especial, para uma base de dados de 8 cidades. As demais seções deste relatório discutem os diversos aspectos de tal implementação e são organizadas conforme a descrição a seguir. Na seção~\ref{estado_da_arte} é apresentada as atuais estratégias existentes para tratar do PCV. Na Seção~\ref{metodologia}, discute-se a metodologia utilizada para a solução proposta. Na Seção~\ref{avaliacao}, avalia-se a aplicação da solução para o PCV. Na Seção 5, analisam-se os resultados dos experimentos. Por fim, apresenta-se as conclusões sobre este trabalho na Seção~\ref{conclusao}. 
